package com.wenhai.leetcode.stack;

import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/max-stack/
 *
 * @author wenhai
 * @date   2021/4/6
 */
public class _716最大栈 {
    private final Stack<Integer> stack;
    private final Stack<Integer> maxStack;
    /** initialize your data structure here. */
    public _716最大栈() {
        this.stack = new Stack<>();
        this.maxStack = new Stack<>();
    }

    public void push(int x) {
        this.stack.push(x);
        pushMaxStack(x);
    }

    private void pushMaxStack(int x) {
        if (maxStack.isEmpty()) {
            maxStack.push(x);
        } else {
            maxStack.push(Math.max(x, maxStack.peek()));
        }
    }

    public int pop() {
        maxStack.pop();
        return this.stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return maxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) {
            buffer.push(pop());
        }
        pop();
        while (!buffer.isEmpty()) {
            push(buffer.pop());
        }
        return max;

    }
}
